//验证回文串 II
/*给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
1 <= s.length <= 105
s 由小写英文字母组成
*/
class Solution {
public:
    bool validPalindrome(string s) {
        int count = 0;
        int left = 0;
        int right = s.size() - 1;
        while (left < right) {
            if (s[left] != s[right]) {
                if (s[left + 1] == s[right]) {
                    int new_left = left + 1;
                    int new_right = right;
                    while (new_left < new_right) {
                        if (s[new_left] != s[new_right])
                            break;
                        new_left++;
                        new_right--;
                    }
                    if (new_left >= new_right)
                        return true;
                }
                if (s[left] == s[right - 1]) {
                    int new_left = left;
                    int new_right = right - 1;
                    while (new_left < new_right) {
                        if (s[new_left] != s[new_right])
                            break;
                        new_left++;
                        new_right--;
                    }
                    if (new_left >= new_right)
                        return true;
                }
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};


 //x 的平方根
 /*给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
*/
class Solution {
public:
    int mySqrt(int x) {
        for (long long i = 0; i <= x; i++) {
            if (i * i > x)
                return i - 1;
            else if (i * i == x)
                return i;
        }
        return 0;
    }
};